def f(n):
    if n<=1:
        return 1
    else:
        return f(n-1)+f(n-2)
print(f(3))



def fib_mem(n,mem={}):
    if n<=1:
        return 1
    else:
        if n-1 in mem:
            a=mem[n-1]
        else:
            fib_mem(n-1,mem={})
        if n-2 in mem:
            b=mem[n-2]
        else:
            fib_mem(n-2,mem={})
        c=a+b
print(f(5))
            


def f(n):
    if n<=1:
        return 1
    else:
        return(f(n-1)+f(n-2))
for i in range(0,4):
    print('f({})={}'.format(i,f(i)))
    
    
    
    
    
#动态规划策略
def fib_table(n):
    lookup = []
    for i in range(1, n+1):
        if i<= 2:
            lookup.append(1)
        else:
            lookup.append(lookup[-1]+lookup[-2])
    return lookup[-1]
if __name__ == '__main__':
    for i in range(1,20):
       # print("\n")
        print(fib_table(i), end=' ')
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    


            